// Copyright 2012 Linuxthink. All rights reserved.
// The Word Filter Project
// wf_processing.cpp
// All the processing functions are here.

#include <iostream>
#include <list>
#include <algorithm>
#include <string>
using namespace std;

// This function will split all strings to valid words.
// The *it iterator points at the current string.
// First, we judge whether the string is all valid.
// If yes, continue. If no, break the string into two substrings, make sure
// the first substring is valid, and judge the second substring, so on and
// so for.
// The newly generated string will be put at the previous position of the
// iterator. So overall the order of the words won't change
void SplitWord(const string valid_word, list<string> &word_list) {
  // Declare functions
  bool IsValid(const string valid_word, const char c);
  int FindFirstValid(const string valid_word, int start_position, string s);
  int FindFirstInvalid(const string valid_word, int start_position, string s);
  
  // Declare variables
  list<string>::iterator it;
  
  // First, we judge whether the string is all valid.
  // If yes, continue. If no, break the string into two substrings, make sure
  // the first substring is valid, and judge the second substring, so on and
  // so for.
  for (it = word_list.begin(); it != word_list.end(); it++) {
    int first_valid_start = FindFirstValid(valid_word, 0, *it);
    int first_valid_end = FindFirstInvalid(valid_word, first_valid_start, *it) 
                          - 1;
    int second_valid_start = FindFirstValid(valid_word,
                                            first_valid_end + 1, *it);
                                            
    if (first_valid_start == -1) { // First case: 0 valid words 
                                   // erase it and it--
      it = word_list.erase(it);
      it--; // Because after erase, *it points at the next one!
      continue;
    } else if (second_valid_start == -1) { // Second case: 1 valid word
                                           // get it out and continue
      string temp_string = *it;
      *it = temp_string.substr(first_valid_start,
                               first_valid_end - first_valid_start + 1);
      continue;
    } else { // Third case: more than 1 valid words
             // get the first one intsert it and it--
      string temp_string_it = *it;
      string temp_string = temp_string_it.substr(
          first_valid_start,
          first_valid_end - first_valid_start + 1);
      *it = temp_string_it.substr(second_valid_start,
                                  temp_string_it.size() - second_valid_start);
      word_list.insert(it, temp_string);
      it--;
      continue;    
    }
  }
}

// Judge a single char, whether it's valid or not
bool IsValid(const string valid_word, const char c) {
  for (int i = 0; i < valid_word.size(); i++) {
    if (c == valid_word[i]) {
      return true;
    }
  }
  return false;
}

// Find the first valid word from the start_position, return the position index
// If cannot find, return -1
int FindFirstValid(const string valid_word, int start_position, string s) {
  bool IsValid(const string valid_word, const char c);
  int first_valid = -1;
  for (int i = start_position; i < s.size(); i++) {
    if (IsValid(valid_word, s[i])) {
      first_valid = i;
      break;
    }
  }
  return first_valid;
}

// Find the first invalid word from the start_position, 
// return the position index. If cannot find, return -1
int FindFirstInvalid(const string valid_word, int start_position, string s) {
  bool IsValid(const string valid_word, const char c);
  int first_invalid = -1;
  for (int i = start_position; i < s.size(); i++) {
    if (!IsValid(valid_word, s[i])) {
      first_invalid = i;
      break;
    }
  }
  return first_invalid;
}

// Deletes the duplicated words, leaving the first occurrence
void DeleteDuplicate(list<string> &word_list) {
  list<string>::iterator it;
  for (it = word_list.begin(); it != word_list.end(); it++) {
    list<string>::iterator it2 = it;
    it2++;
    for (true; it2 != word_list.end(); it2++) {
      if (*it == *it2) {
        it2 = word_list.erase(it2);
        it2--;
      }
    }
  }
}

// Change all the words into lower case
void ChangeToLowerCase(list<string> &word_list) {
  list<string>::iterator it = word_list.begin();
  for (it = word_list.begin(); it != word_list.end(); it++) {
    string temp_string = *it;
    for (int i = 0; i < temp_string.size(); i++) {
      if (temp_string[i] >= 'A' && temp_string[i] <= 'Z') 
        temp_string[i] = temp_string[i] + 32;
    }
    *it = temp_string;
  }
}

// Remove the words that are already in the dictionary
void LookUpDictionary(list<string> &dictionary_list, list<string> &word_list) {
  list<string>::iterator it = dictionary_list.begin();
  for (it = dictionary_list.begin(); it != dictionary_list.end(); it++) {
    list<string>::iterator it2 = word_list.begin();
    for(it2 = word_list.begin(); it2 != word_list.end(); it2++) {
      if (*it == *it2) {
        word_list.erase(it2);
        it2--;
      }
    }
  }
}






